# shell_sort.py

# 1 4 5 2 9 8
#       i
# 0..i-1

def insertion_sort(data):
    n = len(data)

    for i in range(1, n):
        # i = 1
        # j in (0, -1, -1)
        # data[1] < data[0]
        for j in range(i-1, -1, -1):
            if data[j+1] < data[j]:
                data[j+1], data[j] = data[j], data[j+1]
            else:
                break


def insertion_sort_gap(data, gap):
    n = len(data)

    for i in range(gap, n):
        # i = 1
        # j in (0, -1, -1)
        # data[1] < data[0]
        for j in range(i-gap, -1, -gap):
            if data[j+gap] < data[j]:
                data[j+gap], data[j] = data[j], data[j+gap]
            else:
                break


# 对指定间隔先排好序 - 最后一次排序时已经差不多有序
def shell_sort(data):
    gap = len(data)//2
    while gap >= 1:
        insertion_sort_gap(data, gap)
        gap //= 2



import random
data = [random.randint(0, 100) for _ in range(100)]
print(data)
shell_sort(data)
print(data)